A typical data communications network includes many hosts interconnected by various data communication devices. The data communications devices can be routers, bridges, switches, access servers, gateways, hubs, concentrators, proxy servers, repeaters and so forth which exchange data over an interconnection of data links. The data links may be physical connections or may be provided using wireless communication mechanisms. The network allows data to propagate between various applications that execute on the hosts. The hosts are often general purpose computer systems such as personal computers, workstations, minicomputers, mainframes and the like, or the hosts may be more special purpose computer systems or dedicated devices such as web-site kiosks, facsimile or email servers, video servers, audio servers, and so forth. Each computer host couples either physically or via wireless data link to one or more of the data communications devices that form the network. By way of example, many businesses provide a network of computer hosts to allow employees of the business to exchange data, communicate and generally carry out the functions of the business.
Various physical or hardware data communications connection mechanisms allow the hosts to interconnect with the network. Physical data communications connection mechanisms can include modems, transceivers, network interface cards, fiber optic cards, ports and other hardware devices which allow data to be transferred at various data transfer rates (i.e., bandwidths) to and from the hosts and between the data communications devices. For example, certain hosts on a business network may have high-speed network interfaces which provide connections to the network at high data transfer rates such as fractional-T1, T1, E1 or higher, while other hosts may use inexpensive modems or network interface cards that provide much slower maximum data transfer rates to and from the network.
Depending upon a specific use of a host or group of hosts in a network, which often depends on an application running on the host(s), data traveling across portions of the network may require different levels of data service (i.e., data transfer rates or network bandwidth). For example, a backup server (e.g., a high powered computer containing large amounts of data storage) on a typical network used in a business may require a high speed connection to the network to perform nightly backups of data stored on each employee computer. The backup server may, for example, be connected to a fiber optic backbone in the network which offers very high speed data transfer rates. The high speed offered by the fiber optic backbone may allow, for example, data from many employee computers to be simultaneously backed-up by the backup server thus allowing completion of the data backup process for each employee computer before the start of the next business day.
As another example in the business network setting, certain employee computers which rely heavily on data communications applications may require high speed connections to the business network, while other employee computers used, for example, for administrative purposes, may only require low speed network connections. Employees such as engineers using the high speed data communications computers may require high speed network access, while administrative employees using administrative computers may only require minimal network access with low data transfer rates. Within the network itself however, the various data communications devices such as routers, switches and hubs, which channel the data across the network between computer hosts (either during nightly backups, or during the day for employee communications) must be able to distinguish and properly transmit the different flows of data from hosts that require different levels or qualities of data transfer service.
Since many connections, sessions or data traffic flows (i.e., data associated with an end-to-end application or stream) from multiple hosts with potentially different data rates are frequently switched, routed or transferred through the same data communication devices in a network, the data communications devices must provide a way to establish, allocate or reserve the bandwidth requirements for each flow, session, or connection. Once the bandwidth is allocated, the devices must distinguish the different data flows or connections requiring the different levels of service (i.e., different data rates or bandwidth requirements). Once distinguished, the data communications devices must service each connection or flow at its prescribed level of service. For example, if T1 data rates are required for the backup server, the data communications devices must identify and transport backup data through the network at T1 speeds, while other data that may also be present on the network is transferred at some other data rate, such as a xe2x80x9cbest-effort-onlyxe2x80x9d data rate. Management of the various data transmission and propagation requirements associated with data having differing levels of service is a well known problem associated with data communications devices in modem networks.
Various bandwidth allocation or reservation protocols have been developed for use in modem networks to provide guaranteed Quality of Service (QoS) or controlled end-to-end delays for transmitted data. These protocols allow applications that exchange data between sending and receiving hosts (e.g., employee computers and the backup server) to establish reservations of bandwidth over the network for the various services required by the applications. One such protocol is called RSVP, which stands for the Resource ReSerVation Protocol.
As its name implies, computer hosts can use RSVP to request a specific QoS from the network on behalf of an application data stream. When a host needs bandwidth, the host transmits an RSVP bandwidth reservation request message on the network along the path of the session of data communications. RSVP processes in each data communications device in the network propagate the request through the network to each data communications device (e.g., router, switch, hub) or node that the network uses to transport the session data. At each node, the RSVP process for that node attempts to make a resource (i.e. bandwidth) reservation for the stream specified in the RSVP request at that moment in time. As bandwidth is successfully reserved in each node on the network path from sending host to receiving host, the data associated with the session of data communications can use the reserved network bandwidth, while other data streams are excluded from using the reserved bandwidth resources. In other words, the QoS (e.g., data rate or allocated bandwidth) for that stream is generally guaranteed since the bandwidth is reserved in each node for use by that particular stream (e.g., backup data) and no other. When the sending and receiving hosts no longer require the use of the reserved bandwidth, the hosts mutually agree to release the reserved bandwidth via a series of RSVP un-reserve (i.e., tear-down) protocol messages sent to each data communications device on the path of the reserved data. The data communications devices receive the RSVP un-reserve (tear-down) messages and release the formerly reserved bandwidth resources, allowing these resources to be used for the transfer of other data.
FIG. 1 illustrates a typical architecture and data flow of a prior art data communications device 100 configured to use RSVP. Traditionally, to make a resource reservation in the data communications device 100 (e.g. a router), an RSVP process 101 executing on the device 100 receives an RSVP request (not shown) from a host and communicates this request to two local decision modules, admission control 102 and policy control 103. Admission control 102 determines whether the device 100 has sufficient available resources (e.g., buffer capacity, processor and I/O bandwidth) to supply the requested QoS. Policy control 103 determines whether a user, host or application (typically on another device or host) requesting the bandwidth reservation has administrative permission (i.e. access control) to make the reservation. If either check fails, the RSVP process 101 returns an error notification to the application process that originated the request. If both the admission and policy control checks succeed, the RSVP process 101 defines a set of filterspec parameters provided to a packet classifier 104 and a set of flowspec parameters provided to the packet scheduler 106 to configure and obtain the desired QoS in the device 100 for that stream.
The packet classifier 104 uses the filterspec parameters to filter each packet (data in) that arrives at the device to determine the route and queue for the packet within the data queuing mechanism 105. For example, there may be many prioritized queues, each providing a specific level of service or QoS. The packet scheduler 106 uses the flowspec parameters to properly service the queues in the data queuing mechanism 105 to achieve the promised QoS for each stream. Typically, the packet scheduler 106 employs a weighted fair queuing algorithm to de-queue the data from the various queues in the data queuing mechanism 105 according to the bandwidth allocation requirements or QoS defined in the flowspec parameters.
FIG. 2 illustrates a prior art packet data structure 510 used to transport data in a data stream for which RSVP has reserved bandwidth in data communications device 110. The data packet 510 includes an RSVP header field 180 followed by UDP and IP headers 181, 182 and the data 183. The RSVP header 180 typically includes various fields 184 through 191. Of particular interest is the Tspec field 191 which provides a description or identification of the traffic flow, session, or data stream to which this data packet 510 is associated. The packet classifier 104 and the packet scheduler 106 can use the Tspec field 191 to identify different flows of data and enforce the bandwidth allocations or QoS for each identified flow.
Current implementations of bandwidth or resource reservation protocols such as RSVP are fraught with a number of limitations. Overall, the RSVP protocol is static in nature. That is, for each different bandwidth reservation, one or more RSVP protocol path and reservation messages must be communicated between the sending and receiving hosts and all of the data communications devices (e.g. routers, switches, hubs, and so forth) on the path that the data is to take through a network. Thus, once RSVP is used to reserve bandwidth for a particular stream of data, to change the amount of reserved bandwidth requires a new series of RSVP messages to be exchanged, as explained above. No mechanism is provided in current implementations of bandwidth reservation protocols such as RSVP to automatically adjust amounts of reserved bandwidth in data communications devices on-the-fly, without further communications via the reservation protocol.
The RSVP protocol does not define when or how a data communications device (e.g. 100 in FIG. 1) is to implement the actual bandwidth reservations allocated to a session or flow of data communication between hosts. Rather, RSVP simply provides a mechanism to exchange bandwidth reservation and path messages along the path of data communication between sending and receiving hosts. The reservation messages simply identify a session or stream of data communication and indicate a requested level of service for that stream of data. The path messages indicate where the data is to come from and also indicate where to transmit the data.
Since no time limitations are provided in the RSVP protocol, current implementations of RSVP processing interpret RSVP request messages immediately which results in immediate reservations of bandwidth if the request is allowed. That is, a data communications device that receives an RSVP request for a bandwidth reservation performs the policy and admission control processing essentially at the moment the RSVP request is received. If the amount of bandwidth reserved via RSVP is not actually needed until a later point in time (i.e., transmission of the session of data communications that will use the bandwidth has not yet commenced), current implementations of reservation protocols such as RSVP have no way to specify reservations that are to made in the future via information in the RSVP request messages. Currently therefore, bandwidth is reserved in the device even though its actual use may not be needed until a later point in time.
Furthermore, RSVP does not specify the mechanisms to actually set aside or reserve the bandwidth resources within the device itself. Rather, they are dependant upon the implementation of the data communications devices that must interpret the protocol and reserve resources in any particular manner in which they chose.
Accordingly, RSVP only provides a framework for hosts to notify and request immediate reservations of bandwidth in all data communications devices that are on paths between sending and receiving hosts. Once the data communications devices have agreed to reserve the requested bandwidth at the time the RSVP message is received (i.e., admission and policy control), the implementation of how that bandwidth is actually reserved or set aside within each device is left up to the device and is not part of the RSVP protocol. The previously described prior art implementations of device bandwidth reservation mechanisms using customized packet classifiers and packet schedulers which operate in conjunction with the RSVP protocol have become quite popular.
However, another problem that stems from these prior art implementations is that they do not allow adjustments to be made to the amount of bandwidth reserved to a session of data communication over a period of time without requiring the session to be interrupted. That is, once the prior art implementations of bandwidth reservation techniques (i.e. modified classifiers and schedulers) reserve a set amount of bandwidth between two or more hosts immediately upon receipt of the reservation messages, the prior art implementations cannot later adjust the amount of reserved bandwidth via another set of RSVP messages without clearing the session from end-to-end of all data in the path(s) between sending and receiving hosts. This essentially requires the sender(s) to stop sending session data to provide time for all session data in the network to clear and reach the intended receiver(s). In other words, if the bandwidth or QoS requirements of a session need to change over time (e.g., a receiving host determines later that it actually needs more bandwidth to properly receive a stream after the initial reservation request has been completed), a new RSVP negotiation must take place that requires the sending host to halt data transmission for a period of time, while the sending and receiving hosts, and all data communication devices in between, clear themselves of the session data. Then, the sender and receiver must use another set of RSVP reservation and path messages to adjust (i.e., increase or decrease) the amount of bandwidth allocated between the sender and receiver hosts to meet the new requirements at that point in time.
One reason that current implementations of RSVP do not allow future bandwidth adjustments to be made once a communication session is in progress is not completely due to limitations of the RSVP protocol. The design of prior art data communications devices that support RSVP also contributes to these limitations. In the prior art systems that support RSVP (such as that shown in FIG. 1), a customized data classifier 104 and scheduler 106 handle RSVP bandwidth reservation requests and enforce the bandwidth allocation requirements. The RSVP process 101 periodically updates the customized classifier 104 with filterspec information which allows the classifier 104 to properly examine and classify packets of data with the flow identification associated with the packets. If a packet is associated with a flow of data for which bandwidth has been allocated via RSVP, the customized classifier 104, for example, directs this packet to a queue reserved for this flow. Once queued, the customized scheduler 106 typically uses a weighted fair queuing algorithm to dequeue the data from the various queues according to the bandwidth allocation requirements associated with the various flows of data in relation to each queue as defined by the flowspec requirements.
By way of example, if the classifier 104 identifies data associated with a session having a high bandwidth reservation, the classifier 104 may queue the data in a high bandwidth queue. The scheduler 106 may service the high bandwidth queue more frequently than other queues which may have lower bandwidth allocations or reservations which are serviced less frequently. Since the classifier, the scheduler, and sometimes the queuing structure are all involved in prior art device specific implementations of bandwidth reservation using RSVP, data associated with a specific data communications session may exist in any one of these components in the device at any point in time. Hence, if the prior art RSVP process 101 were to attempt to dynamically or automatically change the allocation of reserved bandwidth during an active session of data communication, the scheduler 106 might need to reconfigure queuing structures and the classifier 104 might need to be made aware of the new bandwidth allocation scheme for that session. If such a reconfiguration were attempted during the transfer of session data, significant delays and/or lost data would result for data flows having data that is buffered in the data communications device.
To avoid such losses or delays of data, prior art implementations of RSVP require that the sending host halt the transmission of data and that all data be flushed through the network to the receiver. Once the prior art devices clear the network of any data associated with a specific session of data communication, the prior art devices use another sequence of RSVP messages to adjust bandwidth and establish a new session. Once the prior art devices have established a new bandwidth allocation, a new session of data communication must be reinitiated. This explains why current RSVP protocols and prior art implementations of RSVP in data communications devices do not support the ability to designate future adjustments of modifications that should be made to amounts of reserved bandwidth. That is, since prior art implementations require the session of data communications to generally be broken in order to adjust bandwidth, no implementation of automatic, programmable or future adjustments to bandwidth are provided.
Conversely, the present invention provides techniques which allow a bandwidth reservation protocol such as RSVP to specify future resource reservations and a time at which those reservation should be made, or to specify a time at which a resource reservation (that is either currently reserved or is specified for future reservation in the same reservation message) should be modified. This allows, for example, conservation of network bandwidth since bandwidth is only actually reservedin network devices (e.g., routers, network access servers) at the specified time period(s).
The present invention also avoids the prior art situation of requiring a tear-down or break in a data communication session in order to re-allocate or adjust bandwidth reserved for a session. The present invention provides a device implementation of RSVP that can accept bandwidth allocation changes and can dynamically adjust bandwidth based on different times or events during an active session of data communication without requiring a pause or break in the transmission of data along the entire path of data transmission from sender(s) to receiver(s).
More specifically, embodiments of the present invention provide methods for controlling bandwidth allocation within a data communications device. The methods are generally performed by computing resources within a data communications device. One such method includes the steps of receiving, in the data communications device, bandwidth allocation information indicating future bandwidth allocation modification information associated with a session of data communication. The data communications device of the invention can then determine a future event upon the occurrence of which, the data communications device will modify an amount of bandwidth allocated to the session of data communication. The future event is determined based upon the future bandwidth allocation modification information. The data communications device can then detect the occurrence of the future event in the data communications device and in response to detecting the event, can modify the amount of bandwidth allocated to the session of data communications in the data communications device. In this manner, a data communications device is able to be programmed with bandwidth reservation information that changes, for instance, at certain times defined in the future bandwidth modification information or upon the occurrence of certain specified events.
The bandwidth allocation information may be received in the form of a bandwidth reservation message(s) identifying a session of data communication, an amount of bandwidth to reserve in the data communications device for the session of data communication, and the future bandwidth allocation modification information. Preferably, the bandwidth reservation message is an RSVP reservation message and includes extensions provided by this invention. For instance, an RSVP message indicating future modification information such as a time or event upon the occurrence of which the RSVP bandwidth reservation should be modified is included as an embodiment of this invention.
The future bandwidth allocation modification information can specify predetermined event information upon which the future event is to be determined, and also can specify a bandwidth modification amount indicating an amount by which the amount of bandwidth allocated to the session of data communications should be modified. The predetermined event information can specify, for example, a measure of time in which case the future event is a future time and is determined based on the measure of time specified in the predetermined event information.
Alternatively, the predetermined event information can define a detectable business cycle in which case the future event is a future time and is determined based on detection of the detectable business cycle. In another alternative, the data communications device can receive the bandwidth allocation information from a network policy server in the form of a network policy indicating when and by how much bandwidth the data communications device is to modify the amount of bandwidth allocated to a session of data communication. A network policy server may provide such information, network wide, to configure all data communications devices similarly. The network policy can specify a plurality of sessions of data communications, and for each of the plurality of sessions of data communication, can also specify various amounts of bandwidths to be allocated for each session of data communication at various times of operation of the data communications device.
Thus a network-wide policy that indicates at what times or on upon what events bandwidths or other resources (e.g., choice of routing algorithms, drop policies, error correction algorithm selections, data rates, as so forth) are to be selected can be propagated to each data communications device in a network. Each data communications device can monitor the policy and adjust its configuration upon the occurrence of times or events specified in the policy. In a business environment, for example, the network policy can specify various amounts of bandwidth to be allocated at various times of a day for various data types according to a business cycle for a business operating the data communications device.
The bandwidth allocation information can also be received in the form of a network policy template, in which case the bandwidth allocation modification information includes parameters to be used by the data communications device when determining future events. For example, the data communications device can use a bandwidth prediction algorithm in conjunction with the network policy template and the parameters in the bandwidth allocation information to compute future events specifying when and by how much bandwidth the data communications device is to modify the amount of bandwidth allocated to the session of data communication. Bandwidth prediction algorithms can provide a statistical analysis of the network and can thus determine when bandwidth requirements are high or low for various data types transferred on the network.
Another method is provided by the invention for dynamically adjusting configuration of a data communications device. This method includes the operations of operating a data communications device according to a first configuration which specifies resources within the data communications device to use in transferring data through the data communications device. The first configuration can be a current bandwidth reservation scheme that is already in place within a data communications device, for example. The operation of this method then receives, in the data communications device, configuration change information specifying predetermined modification information specifying a time or event at which to alter the first configuration of the data communications device. The operation then alters the first configuration of the data communications device at the specified time or event to produce a second configuration which specifies device resources within the data communications device to use in transferring data through the data communications device that are different than what was specified in the first configuration. In this manner, the invention allows a device to be programmed once with a first configuration which can automatically be modified into the second configuration without having to re-communicate or re-program the device.
The invention also provides a data communications device which includes an input port that receives bandwidth allocation information indicating future bandwidth allocation modification information associated with a session of data communication. A data transporter coupled to the input port is included, as is a bandwidth reservation processor coupled to the input port and the data transporter. The bandwidth reservation processor receives the bandwidth allocation information from the input port and determines a future event, upon the occurrence of which the bandwidth reservation processor will modify an amount of bandwidth allocated to the session of data communication in the data transporter. The future event is preferably determined based upon the future bandwidth allocation modification information.
In operation, the bandwidth reservation processor detects the occurrence of the future event in the data communications device and, in response to the detecting operation, the bandwidth reservation processor modifies the amount of bandwidth allocated to the session of data communications in the data transporter. The data communications device is thus able to automatically and dynamically adjust bandwidth information without continuous communication concerning bandwidth adjustments provided by hosts or terminals within a network.
The data communications device also includes a computer readable storage area coupled to the bandwidth reservation processor. The bandwidth reservation processor also includes a bandwidth request handler coupled to the input port. The bandwidth request handler receives and stores the bandwidth allocation information in a resource allocation table maintained in the computer readable storage area. A bandwidth labeler is provided and is coupled to the computer readable storage area. A signal provider used to trigger events (times or actual events) is also coupled to the bandwidth labeler. In this configuration, the bandwidth labeler receives a signal provided from the signal provider and monitors the bandwidth allocation information in the resource allocation table for an occurrence of the signal, and upon such occurrence, the bandwidth labeler modifies the amount of bandwidth allocated to the session of data communications in the data transporter.
The signal provider may be a clock providing a time signal or an event signal providing an event signal upon the occurrence of an event. The time signal and the event signal are determined by the bandwidth labeler to match the future event determined by the bandwidth reservation processor. That is, a time provided by the clock or an event provided such as an event (e.g., interrupt) signal can be compared to information in the resource allocation table. When there is a match, the bandwidth is modified, as specified for the particular data type of the session of data communications.
Generally, the bandwidth reservation processor receives the bandwidth allocation information and controls, over a period of time, an amount of bandwidth reserved within the data transporter for transferring data associated with the session of data communication through the data communications device. As noted above, in one configuration, the bandwidth reservation processor controls the amount of bandwidth reserved based on a time schedule determined from the future bandwidth allocation modification information.
The bandwidth reservation processor can detect future times and events specified by just a single bandwidth reservation message. Upon the occurrence of the events or times, the bandwidth reservation processor modifies the amount of bandwidth reserved for a session of data communications without additional bandwidth reservation messages. This saves network bandwidth since only one resource reservation message is needed to instruct a data communications device how to modify bandwidth at future times or in the event of future events.
The invention also provides a computer program product having a computer-readable medium including computer program logic encoded thereon for allocating bandwidth in a data communications device. Generally, when the computer program logic is executed on at least one processing unit with the data communications device (e.g., within the bandwidth reservation processor) the computer program logic can cause the processor to perform one or more of the aforementioned methods of the invention. This embodiment is thus directed to a disk, memory, or other computer readable medium that is encoded with computer code (i.e., software) that includes logic to carry out the methods of the invention. These embodiments need not be resident in a computer system or data communications device. Rather, they may simply exist as software or as a program on some sort of computer readable medium, such as a CD-ROM or hard or floppy disk.
Other embodiments of the invention include an apparatus transmitting a portion of data in a data communications network. This embodiment is generally directed to a data communications device that creates, formats, and then transmits an RSVP message as modified according to the invention as explained herein. The portion of data (i.e., the RSVP message) is formatted as, and comprises, an RSVP reservation request message indicating an amount of bandwidth to be reserved for a session of data communication, and a future time at which to modify the amount of bandwidth reserved for the session of data communication, and an amount by which to modify the amount of bandwidth reserved for the session of data communication upon occurrence of the future time.
Also provided in another embodiment is a data communications device configured with a data structure. The data structure includes an identification of a session of data communication and future bandwidth allocation modification information allowing a data communications device to determine a future event, the occurrence of which causes the data communications device to modify an amount of bandwidth allocated to the session of data communications and an indication of how much to modify the amount of bandwidth reserved for the session of data communication. A data structure configured in this manner may preferably be embodied as an RSVP bandwidth reservation message within a data communications device (i.e., in a memory of a device driver or other processor or on a disk) and can include the identification of a session of data communication and the future bandwidth allocation modification information for that session.
The aforementioned embodiments provide mechanisms offering time or event-based resource allocation for data in packets, cells, frames, or other formats that are transferred on a data communications network. In particular, preferred embodiments of the invention provide the aforementioned augmentations to the RSVP protocol which include the additional time and/or event information (future bandwidth modification information) and the ability of a data communications device to accept this information as either the RSVP message or as a network policy or template and provide timed updates to the reservation of bandwidth and/or other resources such as memory and processor cycles in a data communications device.